"""
   你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统
   如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
   给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额
    example 1:
     输入: [1,2,3,1]
     输出: 4
    example 2:
     输入: [2,7,9,3,1]
     输出: 12
"""
from typing import List


# 典型的动态规划
# 假设有n个房子，前n间能偷窃到的最高金额是dp[n]，前n−1间能偷窃到的最高金额是dp[n−1]，此时向这些房子后加一间房，此房间价值为num
# 加一间房间后：由于不能抢相邻的房子，意味着抢第n+1间就不能抢第n间
# 那么前n+1间房能偷取到的最高金额dp[n+1]一定是以下两种情况的较大值 ：
#       1、不抢第n+1个房间，因此等于前n个房子的最高金额，即dp[n+1]=dp[n]
#       2、抢第n+1个房间，此时不能抢第n个房间；因此等于前n−1个房子的最高金额加上当前房间价值，即dp[n+1] = dp[n-1] + num
# 所以得出结论：dp[n+1] = max(dp[n],dp[n-1]+num)，即dp[n] = max(dp[n-1],dp[n-2]+num)
# dp[n]只与dp[n-1]和dp[n−2]有关系，因此只记录两个结果即可
def house_robber(nums: List[int]) -> int:
    a, b = 0, 0
    for num in nums:
        a, b = max(b + num, a), a
    return a


if __name__ == '__main__':
    print(house_robber([1, 2, 3, 1]))
    print(house_robber([2, 7, 9, 3, 1]))
